# （【示例说明】代码贴核心部分即可，参赛过程尽量详细记录，注意总结和个人成长）
# https://leetcode.com/contest/weekly-contest-456/
# 第456场周赛，2025/6/29
# 排名以及竞赛分变化：
# Rank#510 2193.34 -> 2212.92 (+19.59)
# 手速场AK，前三题都是中等，最后一题困难但也不太难

# A：implementation
class Solution_WC0456A_P3597:
    def partitionString(self, s: str) -> List[str]:
        n = len(s)
        i = 0
        ss = set()
        ans = []
        for j in range(n):
            sub = s[i:j + 1]
            if not sub in ss:
                ss.add(sub)
                ans.append(sub)
                i = j + 1
        return ans

# B: 前后缀线性规划
class Solution_WC0456B_P3598:
    def longestCommonPrefix(self, words: List[str]) -> List[int]:
        def pfc(x, y):
            for i in range(min(len(x), len(y))):
                if x[i] != y[i]:
                    return i
            return min(len(x), len(y))
            
        n = len(words)
        if n == 1:
            return [0]
        elif n == 2:
            return [0, 0]
            
        a = [pfc(s, t) for s, t in pairwise(words)]
        n1 = len(a)
        pre, suf = [0] * n1, [0] * n1
        pre[0] = a[0]
        for i in range(1, n1):
            pre[i] = max(pre[i - 1], a[i])
        suf[-1] = a[-1]
        for i in range(n1 - 2, -1, -1):
            suf[i] = max(suf[i + 1], a[i])

        ans = [0] * n
        for i in range(n):
            if i == 0:
                ans[i] = suf[i + 1]
            elif i == n - 1:
                ans[i] = pre[-2]
            else:
                ans[i] = max(pre[i - 2] if i >= 2 else 0, suf[i + 1] if i + 2 < n else 0, pfc(words[i - 1], words[i + 1]))
                
        return ans

# C：DP/记忆化回溯
class Solution_WC0456C_P3599:
    def minXor(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # dp = [[[-1] * k for _ in range(n)] for _ in range(n)]
        dp = [[-1] * (k + 1) for _ in range(n)]
        def dpdfs(i, p):
            nonlocal n, dp
            if dp[i][p] >= 0:
                return dp[i][p]
            if p == 1:
                sm = 0
                for j in range(i, n):
                    sm ^= nums[j]
                dp[i][p] = sm
                return sm
            ans = 2147483647
            sm = 0
            for j in range(i, n - p + 1):
                sm ^= nums[j]
                ans = min(ans, max(sm, dpdfs(j + 1, p - 1)))
            dp[i][p] = ans
            return ans
        return dpdfs(0, k)

#D：最小生成树+优先队列贪心
class Solution_WC0456D_P3600:
    def maxStability(self, n: int, edges: List[List[int]], k: int) -> int:
        uni = UnionFind(n)
        hd = []
        hp = []
        total = n - 1
        for u, v, w, must in edges:
            if must:
                if uni.check(u, v):
                    return -1
                else:
                    total -= 1
                    uni.union(u, v)
                    heappush(hp, (w, 1))
            else:
                heappush(hd, (-w, u, v)) # hd.append((-w, u, v)) # WA: 低级手误

        while total:
            if not hd:
                return -1
            s, u, v = heappop(hd)
            if not uni.check(u, v):
                w = -s
                uni.union(u, v)
                heappush(hp, (w, 0))
                total -= 1
        
        while k:
            w, upgrade = hp[0]
            if upgrade:
                return w
            else:
                k -= 1
                heapreplace(hp, (w << 1, 1))
        return hp[0][0]
